/*
 * @Author       : wangzeyu 2309335887@qq.com
 * @Date         : 2023-07-23 23:31:56
 * @LastEditors  : WangZeYu
 * @LastEditTime : 2023-08-14 15:33:39
 * @FilePath     : \algorithm\NQueens.js
 * @Description  : N皇后问题
 * 题目描述：际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

 */
/**
 * @param {number} n
 * @return {string[][]}
 */
let solveNQueens = function (n) {
  // 创建棋盘
  let board = new Array(n)
  for (let i = 0; i < n; i++) {
    board[i] = new Array(n).fill('.');
  }
  console.log('board', board);
  let result = [] // 代表皇后位置的二维数组 
  let columns = new Set() // 列集合
  let diagonalUp = new Set() // 对角线上半部分 集合
  let diagonalDown = new Set() // 对角线下半部分 集合

  function backtrack(r) { // r为行数 c为列数
    // return 
    if (r == n) {
      let _board = board.slice()
      for (let i = 0; i < n; i++) {
        _board[i] = _board[i].join('')
      }
      result.push([..._board])
      return
    }
    // 通过循环递归
    for (let c = 0; c < n; c++) {
      if (!columns.has(c) && !diagonalUp.has(r + c) && !diagonalDown.has(r - c)) {
        board[r][c] = 'Q'
        columns.add(c)
        diagonalUp.add(r + c)
        diagonalDown.add(r - c)

        backtrack(r + 1)

        // 撤销选择
        board[r][c] = '.'
        columns.delete(c)
        diagonalUp.delete(r + c)
        diagonalDown.delete(r - c)
      }
    }
  }

  backtrack(0)

  return result
};

console.log(solveNQueens(5));